\documentclass[10pt]{amsart}

\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{fullpage}
\usepackage{graphicx}
\usepackage{tikz}
\usepackage[all]{xy}

\renewcommand{\familydefault}{\sfdefault}
\setlength\parindent{0cm}

\newtheorem*{defn}{Definition}
\DeclareMathOperator{\ord}{ord}
\DeclareMathOperator{\Aut}{Aut}
\DeclareMathOperator{\Prob}{Prob}

\title{Theorem 3.9}
\date{}

\begin{document}
\maketitle

\subsection*{Statement}
Let $G$ be a connected graph, then the following are equivalent:
\begin{enumerate}
\item $G$ is 1-loopy,
\item $G_\text{Irred}$ is strongly connected, and
\item $G$ is not a cycle and as minimal degree at least 2.
\end{enumerate}

\subsection*{Corollary}
If $G$ is a $d$-regular connected graph (for $d \geq 3$), then $G_\text{Irred}$ is strongly connected.

\subsection*{Corollary}
Let $G$ be a 1-loopy graph, then $\ord(G) \geq 1$.

\subsection*{Outline of the proof}
In a 1-loopy graph, one can always find an irreducible which starts with any edge and ends with the reversed edge. This allows to find oriented irreducible paths between any two edges and thus show that the associated graph of irreducible walks is strongly connected. Such a graph clearly cannot contain any leaves or be a cycle since both cases offer edges which do not have irreducible paths to their inverse. Finally one removes any edge from a graph which is not a cycle and which doesn't have any leaves, then none of the remaining connected components can be a tree and hence such a graph must be 1-loopy.

\subsection*{Detailed proof}

\subsubsection*{$(1)\Rightarrow (2)$}
Let $e_1$ and $e_2$ be two directed edges of $\vec{G}$, the completely directed graph issued from $G$. We need to show that there is a directed path in $G_\text{Irred}$ from $e_1$ to $e_2$. For $i=1,2$, say that $e_i$ is an edge in $G$ from the vertex $v_{i1}$ to the vertex $v_{i2}$. Since $G$ is connected, there is an irreducible path from $v_{12}$ to $v_{21}$. This will be a directed path in $G_{\text{Irred}}$ from $e_1$ to $e_2$ unless it starts with the edge $e_1^{-1}$ or it ends with the edge $e_2^{-1}$ in which case it is not irreducible in $G$. We'll show that since $G$ is 1-loopy, we can avoid this.\\

Let us denote that the path from $v_{12}$ to $v_{21}$ is
\[\xymatrix{
v_{11} \ar[r]^{e_1} & v_{12} = w_1 \ar[r]^{f_1} & w_2 \ar[r]^{f_2} & w_3 \ar[r]^{f_3} & \ldots \ar[r]^{f_{k-1}} & w_k \ar[r]^{f_k} & w_{k+1} = v_{21} \ar[r]^{e_2} & v_{22}
}\]
and assume that $f_1 = e_1^{-1}$ and so that $w_2=v_{11}$. Since $G$ is 1-loopy, the connected component of $G \,\backslash \left\{e_1\right\}$ (ACTUALLY NOT $e_1$ BUT THE UNDIRECTED EDGE $(e_1,e_1^{-1})$ INSTEAD, FIND ANOTHER NOTATION) containing the vertex $v_{12}$ is loopy and hence we can find an irreducible loop from that vertex to itself. Denote that path by
\[\xymatrix{
v_{12} \ar[r]^{g_1} & \ar[r]^{g_2} & \ldots \ar[r]^{g_{s-1}} & \ar[r]^{g_s} & v_{12}
}\]
Since none of the edges $g_i$ is either $e_1$ or $e_1^{-1}$ the path
\[\xymatrix{
v_{11} \ar[r]^{e_1} & v_{12} \ar[r]^{g_1} & \ar[r]^{g_2} & \ldots \ar[r]^{g_{s-1}} & \ar[r]^{g_s} & v_{12} = w_1 \ar[r]^{f_1} & w_2 \ar[r]^{f_2} & w_3 \ar[r]^{f_3} & \ldots \ar[r]^{f_{k-1}} & w_k \ar[r]^{f_k} & w_{k+1} = v_{21}
}\]
is irreducible. The same can be used on the edge $f_k$ if it is the edge $e_2^{-1}$ and we end up showing that $G_\text{Irred}$ is strongly connected.

\subsubsection*{$(2)\Rightarrow (3)$}
If $G$ is a cycle, than there can never be an irreducible path from any oriented edge to its inverse. If $G$ has any vertex $v$ of degree 1, then there cannot be an irreducible path from the oriented edge in-coming at that vertex to the oriented edge out-coming there. Both contradict our assumption that $G_\text{Irred}$ is strongly connected.

\subsubsection*{$(3)\Rightarrow (1)$}
Let $e$ be any edge of the graph $G$. There are two cases to consider. First, assume that $G \,\backslash \left\{ e \right\}$ is connected. Assume by contradiction that it is a tree.
\begin{itemize}
\item If that tree has only 1 leaf, then $G$ is a vertex with a self-loop, which is a cycle, so this is a contradiction.
\item If that tree has exactly 2 leaves, that tree is a path and so the edge $e$ either closes the path into a cycle (contradiction!) or is a self-loop attached to a vertex, in which case $G$ has a vertex of degree 1 (contradiction!)
\item If that tree has 3 leaves or more, then $G$ must contain at least one vertex of degree 1 (contradiction!)
\end{itemize}
Now, assume that $G \,\backslash \left\{ e \right\}$ has two connected components. Such a connected component cannot be a tree since it would imply that $G$ has at least one vertex of degree 1 (contradition).
Hence $G$ is 1-loopy.


\end{document}